An online map service can provide virtual maps to one or more user devices. The virtual maps can include land features (e.g., houses, office buildings, or shops). The land features can be positioned along a street in a virtual map based on their locations. To display a land feature in the virtual map, the online map service can determine a location (e.g., latitude and longitude coordinates) of the land feature by geocoding an address (e.g., a street address) of the land feature. An exemplary technique of geocoding is address interpolation. In address interpolation, the online map service can determine geographic coordinates of a street using publicly available data, determine a segment of the street (e.g., a block) using cross street information, determine a number of addresses in the segment (e.g., N street numbers) in the segment, and interpolate the geographic coordinates of each address based on geographic coordinates of the segment and the number of addresses in the segment.